package com.hyb.algorithm.data.struct.dp;

/**
 * @author: ybhu
 * @create: 2021/08/31 07:41
 */
public class MaxProfit {

    public static void main(String[] args) {

        int[] prices=new int[]{7,1,5,3,6,4};

        MaxProfit exe=new MaxProfit();

       int ret= exe.maxProfix2(prices);

        System.out.println(ret);

    }

    public int maxProfix2(int[] prices){
        int n = prices.length;
        int[][] dp = new int[n][2];
        for (int i = 0; i < n; i++) {
            if (i - 1 == -1) {
                dp[i][0] = 0;
                // 解释：
                //   dp[i][0]
                // = max(dp[-1][0], dp[-1][1] + prices[i])
                // = max(0, -infinity + prices[i]) = 0
                dp[i][1] = -prices[i];
                //解释：
                //   dp[i][1]
                // = max(dp[-1][1], dp[-1][0] - prices[i])
                // = max(-infinity, 0 - prices[i])
                // = -prices[i]
                continue;
            }
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
        }
        return dp[n - 1][0];
    }

    //只交易一次 所以 k=0;
    public int maxProfit(int[] prices) {

        int n = prices.length;
        int[][] dp = new int[n][2];

        for (int i = 0; i < n; i++) {

            if (i == 0) {
                //  dp[0][0]=Math.max(dp[-1][0],dp[-1][1]+prices[0]);
                dp[0][0] = 0;
                //dp[0][1]=Math.max(dp[-1][1],dp[-1][0]-prices[i]);
                //dp[-1][1]  dp[-1][1]
                dp[0][1] = -prices[i];
                continue;
            }

            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1],  - prices[i]);
        }

        return dp[n - 1][0];
    }
}
